package mine.code.day.year2021.month09;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个单词数组和一个长度maxWidth，重新排版单词，使其成为每行恰好有maxWidth个字符，且左右两端对齐的文本。
 * 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格' '填充，
 * 使得每行恰好有 maxWidth个字符。
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 * 说明:
 * <p>
 * 单词是指由非空格字符组成的字符序列。
 * 每个单词的长度大于 0，小于等于maxWidth。
 * 输入单词数组 words至少包含一个单词。
 * 示例:
 * <p>
 * 输入:
 * words = ["This", "is", "an", "example", "of", "text", "justification."]
 * maxWidth = 16
 * 输出:
 * [
 * "This  is  an",
 * "example of text",
 * "justification. "
 * ]
 * <p>
 * 示例2:
 * <p>
 * 输入:
 * words = ["What","must","be","acknowledgment","shall","be"]
 * maxWidth = 16
 * <p>
 * 输出:
 * [
 * "What  must  be",
 * "acknowledgment ",
 * "shall be    "
 * ]
 * <p>
 * 解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
 * 因为最后一行应为左对齐，而不是左右两端对齐。
 * 第二行同样为左对齐，这是因为这行只包含一个单词。
 * <p>
 * 示例3:
 * <p>
 * 输入:
 * words = ["Science","is","what","we","understand","well","enough","to","explain",
 * "to","a","computer.","Art","is","everything","else","we","do"]
 * maxWidth = 20
 * <p>
 * 输出:
 * [
 * "Science is what we",
 * "understand   well",
 * "enough to explain to",
 * "a computer. Art is",
 * "everything else we",
 * "do         "
 * ]
 */
public class Day09_文本左右对齐 {

    @Test
    public void run() {
        String[] words = {"What","must","be","acknowledgment","shall","be"};
        int maxWidth = 16;
//        System.out.println(fullJustify(words, maxWidth));
        for (String s : fullJustify(words, maxWidth)) {
            System.out.println(s);
        }
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        int tempLength = -1;
        int[] startIndex = new int[words.length];
        startIndex[0] = 1;
        for (int i = 0; i < words.length; i++) {
            if (tempLength + words[i].length() + 1 > maxWidth) {
                startIndex[i] = 1;
                tempLength = words[i].length();
                continue;
            }
            tempLength += words[i].length() + 1;
        }
        List<String> tempList = new ArrayList<>();
        List<String> result = new ArrayList<>();
        for (int i = 0; i < startIndex.length; i++) {

            if (startIndex[i] == 1) {
                String convert = convert(tempList.toArray(new String[0]), maxWidth);
                if (convert != null) {
                    result.add(convert);
                }
                tempList.clear();
            } else {
                tempList.add(" ");
            }
            tempList.add(words[i]);
            if (i == startIndex.length - 1) {
                String convert = convert(new String[]{String.join("",tempList)}, maxWidth);
                result.add(convert);
            }
        }
        return result;
    }
    private String convert(String[] tempList, int maxWidth) {
        if (tempList.length == 0) {
            return null;
        }
        if (tempList.length == 1) {
            StringBuilder s = new StringBuilder(tempList[0]);
            int length = s.length();
            for (int i = 0; i < maxWidth - length; i++) {
                s.append(" ");
            }
            return s.toString();
        }
        int i = 1;
        while (String.join("", tempList).length() < maxWidth) {
            tempList[i] += " ";
            i = (i + 2) % (tempList.length - 1);
        }
        return String.join("", tempList);
    }
}
